package top.minuy.algorithm.search.string;

/**
 * 字符串匹配算法
 *
 * @author Minuy
 * @time 15:35
 * @date 2021/11/12
 */
public class SubstringMatch {
    private SubstringMatch() {
    }

    /**
     * 字符串暴力搜索算法
     *
     * @param source 源字符串
     * @param target 搜索字符串
     * @return int 被搜索字符串第一次出现的位置，没有找到返回-1
     * @author Minuy
     * @date 2021/11/12 15:48
     */
    public static int bruteForce(String source, String target) {
        // 如果最后的长度小于目标字符串的长度可以不用进行匹配了，一定不存在
        int end = source.length() - target.length() + 1;
        // [0,source.length()-target.length()]
        for (int i = 0; i < end; i++) {
            if (source.charAt(i) == target.charAt(0)) {
                boolean isMatch = true;
                for (int j = 1; j < target.length(); j++) {
                    if (source.charAt(i + j) != target.charAt(j)) {
                        isMatch = false;
                        break;
                    }
                }
                if (isMatch) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 滚动哈希搜索
     *
     * @param s 源字符串
     * @param t 目标字符串
     * @return int 目标字符串所在位置，没找到返回-1
     * @author Minuy
     * @date 2021/11/13 12:22
     */
    public static int rabinKarp(String s, String t) {
        if (t.length() > s.length()) {
            return -1;
        } else if (t.length() == 0) {
            return 0;
        }

        final long MOD = (long) (1e9 + 7); // 较大的素数
        final int B = 256; // 256进制


        long targetHash = 0;  // 目标哈希
        // 求出目标字符串的哈希值
        for (int i = 0; i < t.length(); i++) {
            targetHash = ((targetHash * B) + t.charAt(i)) % MOD;
        }


        long sourceHash = 0; // 滚动哈希
        long P = 1; // 最高位
        // 求出搜索字符串的前 t.length-1 个字符组成的字符串的哈希值
        for (int i = 0; i < t.length() - 1; i++) {
            sourceHash = ((sourceHash * B) + s.charAt(i)) % MOD;
        }
        // 求出最高位单位值，最高位应该是t.length - 1
        for (int i = 0; i < t.length() - 1; i++) {
            P = (P * B) % MOD;
        }

        // 滚动搜索
        // 循环不变量：sourceHash = [i - t.length()+1, i-1] 的哈希值
        for (int i = t.length() - 1; i < s.length(); i++) {
            // 获得一个与目标长度相等的源哈希值
            sourceHash = ((sourceHash * B) + s.charAt(i)) % MOD;

            // 判断哈希值是否相等，相等则看是不是哈希冲突
            if (sourceHash == targetHash && contrast(s, i - t.length() + 1, t)) {
                return i - t.length() + 1;
            }

            // 删去最高位后的哈希值
            // 同样的也是减去原来的t长度位，但是这个长度位可能会太大，需要先求余再减
            // 那么同样的两个余数就可能会是负数，所以要加上一个余数，那如果不是负数就又大于MOD了
            // 所以最后再对MOD求余
            sourceHash = ((sourceHash - ((s.charAt(i - t.length() + 1) * P) % MOD)) + MOD) % MOD;
        }

        return -1;
    }

    /**
     * 对比两个子字符串是否相同 [i,i+t.length) 与 t
     *
     * @param s 源字符串
     * @param i 源字符串开始索引
     * @param t 目标字符串
     * @return boolean 是否相同
     * @author Minuy
     * @date 2021/11/13 12:05
     */
    private static boolean contrast(String s, int i, String t) {
        for (int j = 0; j < t.length(); j++) {
            if (s.charAt(i + j) != t.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 学习KMP结束
     * 做个重载，网上资料太乱了，一团乱，好不容易理顺，QWQ
     *
     * @param t 文本（要被查找的）
     * @param p 模式（要查找的）
     * @return int 模式在文本中匹配的第一个索引，匹配失败返回-1
     * @author Minuy
     * @date 2021/11/14 20:46
     */
    public static int KMP(String t, String p) {
        return KMP(t, p, false);
    }

    /**
     * KMP 算法实现模式匹配
     *
     * @param t 文本（要被查找的）
     * @param p 模式（要查找的）
     * @return int 模式在文本中匹配的第一个索引，匹配失败返回-1
     * @author Minuy
     * @date 2021/11/13 16:38
     */
    public static int KMP(String t, String p, boolean isDebug) {
        if (p.length() > t.length()) {
            return -1;
        } else if (p.length() == 0) {
            return 0;
        }
        int[] next;
        if (isDebug) {
            next = getNext(p);
            System.out.println("传统 next：");
            for (int i = 0; i < next.length; i++) {
                System.out.print(next[i]);
                if (i != next.length - 1) {
                    System.out.print(',');
                }
            }
            System.out.println();
            System.out.println("改进 next：");
            next = getNextNew(p);
            for (int i = 0; i < next.length; i++) {
                System.out.print(next[i]);
                if (i != next.length - 1) {
                    System.out.print(',');
                }
            }
            System.out.println();
        } else {
            next = getNextNew(p);
        }

        int i = 0, j = 0;
        // t没有匹配完 并且 没有p也没有被匹配完
        while (i < t.length()/*这里不能像BF那样提前返回，不知道哪是失配点*/ && j < p.length()) {
            // 如果成功匹配，各自下推一位
            if (-1 == j || t.charAt(i) == p.charAt(j)) {
                j++;
                i++;
            } else {
                // 否则回溯
                j = next[j];
            }
        }

        // 模式串全部匹配成功
        if (j == p.length()) {
            return i - j;
        }

        return -1;
    }

    public static void main(String[] args) {
        String t = "wwwwwww.23";
        String p = "wwwwww.";
        System.out.println("自己的算法：" +
                KMP(t, p, true));
        System.out.println("系统的算法："+t.indexOf(p));
    }

    /**
     * 原始的next函数
     *
     * @param p 要预处理的模式串
     * @return int[] next 数组
     * @author Minuy
     * @date 2021/11/14 20:49
     */
    private static int[] getNext(String p) {
        int[] next = new int[p.length()];
        int i = 0, j = -1;
        next[0] = -1;
        while (i < next.length - 1) {
            if (-1 == j || p.charAt(j) == p.charAt(i)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    /**
     * 优化后的next函数
     *
     * @param p 要预处理的模式串
     * @return int[] next 数组
     * @author Minuy
     * @date 2021/11/14 20:48
     */
    private static int[] getNextNew(String p) {
        int[] next = new int[p.length()];
//        next[0] = -1;
//        for (int i = 1, j = -1; i < s.length(); i++) {
//            while (j != -1 && s.charAt(i) != s.charAt(j + 1)) j = next[j];
//            if (s.charAt(i) == s.charAt(j + 1)) j += 1;
//            next[i] = j;
//        }

//        next[0] = -1;
//        for (int i = 1,j = -1; i < s.length(); i++) {
//            if (s.charAt(j + 1) == s.charAt(i)) {
//                j++; // 如果遇到相同的，往下走
//            } else  {
//                // 如果不同，且j！=-1的，回溯
//                if(j!=-1) {
//                    j = next[j];
//                }
//            }
//            next[i] = j; // 记录j的值
//        }

        int i = 0, j = -1;
        next[0] = -1;
        while (i < next.length - 1) {
            if (-1 == j || p.charAt(j) == p.charAt(i)) {
                i++;
                j++;
                // next[i] = j;

                //出现了p[next[j]] = p[j]的情况，则把next[j]的值再次递归
                if (p.charAt(i) == p.charAt(j)) {
                    next[i] = next[j];
                } else {
                    next[i] = j;
                }
            } else {
                j = next[j];
            }
        }
        return next;
    }

}
